1649D - Integral Array - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define ppi pair<int,int>
#define ppl pair<ll,ll>
#define pb push_back
#define endl '\n'
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()


const int mod = 1e9 + 7;
const ll inf = LONG_LONG_MAX;
const int modt = 998244353;

ll Sqrt(ll n) {
    ll s = 1, e = 1e9;

    while (s <= e) {
        ll mid = (s + e) >> 1;

        if (mid * mid > n) e = mid - 1;
        else s = mid + 1;
    }
    return e;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int tt;
    cin >> tt;
    while (tt--) {
        ll n, c;
        cin >> n >> c;
        vector<int> a(c + 1), pfx(c + 1);
        bool ans = true;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            a[x]++;
        }
        for (int i = 1; i <= c; i++) {
            if (a[i] > 1 && a[1] == 0) ans = false;
            a[i] = min(a[i], 1);
            pfx[i] = a[i] + pfx[i - 1];
        }
        if (!ans) {
            cout << "NO" << endl;
            continue;
        }
        for (ll i = 1; i <= c; i++) {
            if (!a[i]) continue;
            for (int j = 1; j <= (c / i); j++) {
                //if (j == i) continue;
                ll x = i * j;
                ll y = min(i * (j + 1) - 1, c);
                if (y < x) continue;
                int p = pfx[y] - pfx[x - 1];
                if (p && !a[j]) ans = false;
            }
        }
        cout << (ans ? "YES" : "NO") << endl;
    }
}